home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / NEWSOFT / MAY / MP3CONV / !MP3Conv / c / huffman < prev    next >
Text File  |  1997-02-17  |  11KB  |  397 lines
  1. /**********************************************************************
  2.  * ISO MPEG Audio Subgroup Software Simulation Group (1996)
  3.  * ISO 13818-3 MPEG-2 Audio Decoder - Lower Sampling Frequency Extension
  4.  *
  5.  * $Id: huffman.c,v 1.2 1996/03/28 03:13:37 rowlands Exp $
  6.  *
  7.  * $Log: huffman.c,v $
  8.  * Revision 1.2  1996/03/28 03:13:37  rowlands
  9.  * Merged layers 1-2 and layer 3 revisions
  10.  *
  11.  * Revision 1.1  1996/02/14 03:45:52  rowlands
  12.  * Initial revision
  13.  *
  14.  * Received from FhG
  15.  **********************************************************************/
  16. /**********************************************************************
  17.  *   date   programmers                comment                        *
  18.  *27.2.92   F.O.Witte                  (ITT Intermetall)              *
  19.  *                       email: otto.witte@itt-sc.de    *
  20.  *                       tel:   ++49 (761)517-125          *
  21.  *                       fax:   ++49 (761)517-880          *
  22.  *12.6.92   J. Pineda                  Added sign bit to decoder.     *
  23.  * 08/24/93 M. Iwadare                 Changed for 1 pass decoding.   *
  24.  *--------------------------------------------------------------------*
  25.  *  7/14/94 Juergen Koller      Bug fixes in Layer III code           *
  26.  *--------------------------------------------------------------------*
  27.  * 12/16/96 Johan Hagman    Adapted for Solaris (mpeg3play 0.9)   *
  28.  *********************************************************************/    
  29.  
  30. #include "common.h"
  31. #include "huffman.h"
  32. #include "stdlib.h"
  33.      
  34. HUFFBITS dmask = (HUFFBITS)1 << (sizeof(HUFFBITS)*8-1);
  35. unsigned int hs = sizeof(HUFFBITS)*8;
  36.  
  37. struct huffcodetab ht[HTN];    /* array of all huffcodtable headers    */
  38.                 /* 0..31 Huffman code table 0..31    */
  39.                 /* 32,33 count1-tables            */
  40.  
  41. /* read the huffman encode table */
  42. int read_huffcodetab(FILE *fi)
  43. {
  44.  
  45.   char line[100],command[40],huffdata[40];
  46.   unsigned int t,i,j,k,nn,x,y,n=0;
  47.   unsigned int xl, yl, len;
  48.   HUFFBITS h;
  49.   int    hsize;
  50.   
  51.   hsize = sizeof(HUFFBITS)*8; 
  52.   do {
  53.       fgets(line,99,fi);
  54.   } while ((line[0] == '#') || (line[0] < ' ') );
  55.   
  56.   do {    
  57.     while ((line[0]=='#') || (line[0] < ' ')) {
  58.       fgets(line,99,fi);
  59.     } 
  60.  
  61.     sscanf(line,"%s %s %u %u %u",command,ht[n].tablename,
  62.                      &xl,&yl,&ht[n].linbits);
  63.     if (strcmp(command,".end")==0)
  64.       return n;
  65.     else if (strcmp(command,".table")!=0) {
  66.       fprintf(stderr,"huffman table %u data corrupted\n",n);
  67.       return -1;
  68.     }
  69.     ht[n].linmax = (1<<ht[n].linbits)-1;
  70.    
  71.     sscanf(ht[n].tablename,"%u",&nn);
  72.     if (nn != n) {
  73.       fprintf(stderr,"wrong table number %u\n",n);
  74.       return(-2);
  75.     } 
  76.  
  77.     ht[n].xlen = xl;
  78.     ht[n].ylen = yl;
  79.  
  80.     do {
  81.       fgets(line,99,fi);
  82.     } while ((line[0] == '#') || (line[0] < ' '));
  83.  
  84.     sscanf(line,"%s %u",command,&t);
  85.     if (strcmp(command,".reference")==0) {
  86.       ht[n].ref   = t;
  87.       ht[n].table = ht[t].table;
  88.       ht[n].hlen  = ht[t].hlen;
  89.       if ( (xl != ht[t].xlen) ||
  90.            (yl != ht[t].ylen)  ) {
  91.         fprintf(stderr,"wrong table %u reference\n",n);
  92.         return (-3);
  93.       };
  94.       do {
  95.         fgets(line,99,fi);
  96.       } while ((line[0] == '#') || (line[0] < ' ') );
  97.     } 
  98.     else {
  99.       ht[n].ref  = -1;
  100.       ht[n].table=(HUFFBITS *) calloc(xl*yl,sizeof(HUFFBITS));
  101.       if (ht[n].table == NULL) {
  102.          fprintf(stderr,"unsufficient heap error\n");
  103.          return (-4);
  104.       }
  105.       ht[n].hlen=(unsigned char *) calloc(xl*yl,sizeof(unsigned char));
  106.       if (ht[n].hlen == NULL) {
  107.          fprintf(stderr,"unsufficient heap error\n");
  108.          return (-4);
  109.       }
  110.       for (i=0; i<xl; i++) {
  111.         for (j=0;j<yl; j++) {
  112.       if (xl>1) 
  113.             sscanf(line,"%u %u %u %s",&x, &y, &len,huffdata);
  114.       else 
  115.             sscanf(line,"%u %u %s",&x,&len,huffdata);
  116.           h=0;k=0;
  117.       while (huffdata[k]) {
  118.             h <<= 1;
  119.             if (huffdata[k] == '1')
  120.               h++;
  121.             else if (huffdata[k] != '0'){
  122.               fprintf(stderr,"huffman-table %u bit error\n",n);
  123.               return (-5);
  124.             };
  125.             k++;
  126.           };
  127.           if (k != len) {
  128.            fprintf(stderr,
  129.               "warning: wrong codelen in table %u, pos [%2u][%2u]\n",
  130.            n,i,j);
  131.           };
  132.           ht[n].table[i*xl+j] = h;
  133.           ht[n].hlen[i*xl+j] = (unsigned char) len;
  134.       do {
  135.             fgets(line,99,fi);
  136.           } while ((line[0] == '#') || (line[0] < ' '));
  137.         }
  138.       }
  139.     }
  140.     n++;
  141.   } while (1);
  142. }
  143.  
  144. #ifndef BUILTIN_TABLES
  145.  
  146. /* Read the huffman decoder table */
  147. int read_decoder_table(FILE *fi)
  148. {
  149.     int            n, i, nn, t;
  150.     unsigned int    v0, v1;
  151.     char        command[100], line[100];
  152.  
  153.     for (n = 0; n < HTN; n++) {
  154.     /* .table number treelen xlen ylen linbits */ 
  155.     do {
  156.         fgets(line, 99, fi);
  157.     } while ((line[0] == '#') || (line[0] < ' '));
  158.      
  159.     sscanf(line,"%s %s %u %u %u %u", command, ht[n].tablename,
  160.         &ht[n].treelen, &ht[n].xlen, &ht[n].ylen, &ht[n].linbits);
  161.     if (strcmp(command, ".end") == 0)
  162.         return n;
  163.     else if (strcmp(command,".table") != 0) {
  164.         fprintf(stderr, "huffman table %u data corrupted\n",n);
  165.         return -1;
  166.     }
  167.     ht[n].linmax = (1 << ht[n].linbits) - 1;
  168.    
  169.     sscanf(ht[n].tablename, "%u", &nn);
  170.     if (nn != n) {
  171.         fprintf(stderr, "wrong table number %u\n", n);
  172.         return -2;
  173.     } 
  174.     do {
  175.         fgets(line, 99, fi);
  176.     } while ((line[0] == '#') || (line[0] < ' '));
  177.  
  178.     sscanf(line, "%s %u", command, &t);
  179.  
  180.     if (strcmp(command, ".reference") == 0) {
  181.         ht[n].ref        = t;
  182.         ht[n].val        = ht[t].val;
  183.         ht[n].treelen    = ht[t].treelen;
  184.         if ((ht[n].xlen != ht[t].xlen) || (ht[n].ylen != ht[t].ylen)) {
  185.         fprintf(stderr,"wrong table %u reference\n",n);
  186.         return -3;
  187.         };
  188.         while ((line[0] == '#') || (line[0] < ' ') ) {
  189.         fgets(line,99,fi);
  190.         }
  191.  
  192.     } else if (strcmp(command,".treedata") == 0) {
  193.  
  194.         ht[n].ref    = -1;
  195.         ht[n].val    = (unsigned char (*)[2]) 
  196.         calloc(2 * (ht[n].treelen), sizeof(unsigned char));
  197.         if (ht[n].val == NULL) {
  198.         fprintf(stderr, "huffman.c: heap error at table %d\n", n);
  199.         exit(-10);
  200.         }
  201.         for (i = 0; i < ht[n].treelen; i++) {
  202.         fscanf(fi, "%x %x", &v0, &v1);
  203.         ht[n].val[i][0] = (unsigned char)v0;
  204.         ht[n].val[i][1] = (unsigned char)v1;
  205.         }
  206.         fgets(line, 99, fi);    /* read the rest of the line */
  207.  
  208.     } else {
  209.         fprintf(stderr,"huffman decodertable error at table %d\n",n);
  210.     }
  211.     }
  212.     return n;
  213. }
  214.  
  215. #endif
  216.  
  217.  
  218. /* do the huffman coding,  */
  219. /* note! for counta,countb - the 4 bit value is passed in y, set x to 0 */
  220. /* return value: 0-no error, 1 decode error                */
  221. void huffman_coder(
  222.     unsigned int x,         /* x-value */
  223.     unsigned int y,         /* y-value */
  224.     struct huffcodetab *h,     /* pointer to huffman code record  */
  225.     Bit_stream_struc *bs)    /* pointer to open write bitstream */
  226. {
  227.   HUFFBITS huffbits; /* data left aligned */
  228.   HUFFBITS linbitsX; 
  229.   HUFFBITS linbitsY;
  230.   unsigned int len;
  231.   unsigned int xl1 = h->xlen-1;
  232.   unsigned int yl1 = h->ylen-1;
  233.   linbitsX = 0;
  234.   linbitsY = 0;
  235.   if (h->table == NULL) return;
  236.   if (((x < xl1) || (xl1==0)) && (y < yl1)) {
  237.     huffbits = h->table[x*(h->xlen)+y];
  238.     len = h->hlen[x*(h->xlen)+y];
  239.     putbits(bs,huffbits,len);
  240.     return;
  241.   }  
  242.   else if (x >= xl1) {
  243.     linbitsX = x-xl1;
  244.     if (linbitsX > h->linmax) {
  245.       fprintf(stderr,"warning: Huffman X table overflow\n");
  246.       linbitsX= h->linmax;
  247.     };
  248.     if (y >= yl1) {
  249.       huffbits = h->table[(h->ylen)*(h->xlen)-1];
  250.       len = h->hlen[(h->ylen)*(h->xlen)-1];
  251.       putbits(bs,huffbits,len);
  252.       linbitsY = y-yl1;
  253.       if (linbitsY > h->linmax) {
  254.         fprintf(stderr,"warning: Huffman Y table overflow\n");
  255.         linbitsY = h->linmax;
  256.       };
  257.       if (h->linbits) {
  258.         putbits(bs,linbitsX,h->linbits);
  259.         putbits(bs,linbitsY,h->linbits);
  260.       }
  261.     } 
  262.     else { /* x>= h->xlen, y<h->ylen */
  263.       huffbits = h->table[(h->ylen)*xl1+y];
  264.       len = h->hlen[(h->ylen)*xl1+y];
  265.       putbits(bs,huffbits,len);
  266.       if (h->linbits) {
  267.         putbits(bs,linbitsX,h->linbits);
  268.       }
  269.     }
  270.   }
  271.   else  { /* ((x < h->xlen) && (y>=h->ylen)) */
  272.     huffbits = h->table[(h->ylen)*x+yl1];
  273.     len = h->hlen[(h->ylen)*x+yl1];
  274.     putbits(bs,huffbits,len);
  275.     linbitsY = y-yl1;
  276.     if (linbitsY > h->linmax) {
  277.       fprintf(stderr,"warning: Huffman Y table overflow\n");
  278.       linbitsY = h->linmax;
  279.     };
  280.     if (h->linbits) {
  281.        putbits(bs,linbitsY,h->linbits);
  282.     }
  283.   }
  284. }
  285.  
  286.  
  287. /*
  288.  *  Do the huffman-decoding
  289.  *  Note! for counta,countb -the 4 bit value is returned in y, discard x
  290.  */
  291. int huffman_decoder(
  292.     struct huffcodetab *h,    /* pointer to huffman code record*/
  293.     /* unsigned */ int *x,     /* returns decoded x value*/
  294.     /* unsigned */ int *y,    /* returns decoded y value*/
  295.     int *v,
  296.     int *w)
  297. {  
  298.     HUFFBITS    level;
  299.     int        point = 0;
  300.     int        error = 1;
  301.  
  302.     level = dmask;
  303.     if (h->val == NULL)
  304.     return 2;
  305.  
  306.     /* Table 0 needs no bits */
  307.     if ( h->treelen == 0) {
  308.     *x = *y = 0;
  309.     return 0;
  310.     }
  311.  
  312.     /* Lookup in Huffman table */
  313.  
  314.     do {
  315.     if (h->val[point][0]==0) {    /* end of tree */
  316.         *x = h->val[point][1] >> 4;
  317.         *y = h->val[point][1] & 0xf;
  318.  
  319.         error = 0;
  320.         break;
  321.     } 
  322.     if (hget1bit()) {
  323.         while (h->val[point][1] >= MXOFF) point += h->val[point][1]; 
  324.         point += h->val[point][1];
  325.     } else {
  326.         while (h->val[point][0] >= MXOFF) point += h->val[point][0]; 
  327.         point += h->val[point][0];
  328.     }
  329.     level >>= 1;
  330.     } while (level || (point < ht->treelen) );
  331.   
  332.     /* Check for error */
  333.   
  334.     if (error) { /* set x and y to a medium value as a simple concealment */
  335.     fprintf(stderr, "Illegal Huffman code in data.\n");
  336.     *x = ((h->xlen-1) << 1);
  337.     *y = ((h->ylen-1) << 1);
  338.     }
  339.  
  340.     /* Process sign encodings for quadruples tables */
  341.  
  342.     if (h->tablename[0] == '3' && (h->tablename[1] == '2' ||
  343.             h->tablename[1] == '3')) {
  344.     *v = (*y>>3) & 1;
  345.     *w = (*y>>2) & 1;
  346.     *x = (*y>>1) & 1;
  347.     *y = *y & 1;
  348.  
  349.     /* v, w, x and y are reversed in the bitstream. */
  350.     /* Switch them around to make test bistream work.*/
  351.      
  352.     /* {int i=*v; *v=*y; *y=i; i=*w; *w=*x; *x=i;}  MI */
  353.  
  354.     if (*v) {
  355.         if (hget1bit() == 1)
  356.         *v = -*v;
  357.     }
  358.     if (*w) {
  359.         if (hget1bit() == 1)
  360.         *w = -*w;
  361.     }
  362.     if (*x) {
  363.         if (hget1bit() == 1)
  364.         *x = -*x;
  365.     }
  366.     if (*y) {
  367.         if (hget1bit() == 1)
  368.         *y = -*y;
  369.     }
  370.     } else {
  371.     /* Process sign and escape encodings for dual tables */
  372.  
  373.     /* x and y are reversed in the test bitstream.*/
  374.     /* Reverse x and y here to make test bitstream work.*/
  375.  
  376.     /*    removed 11/11/92 -ag  
  377.      *    {int i=*x; *x=*y; *y=i;} 
  378.      */      
  379.  
  380.     if (h->linbits)
  381.         if ((h->xlen-1) == *x) 
  382.         *x += hgetbits(h->linbits);
  383.     if (*x) {
  384.         if (hget1bit() == 1)
  385.         *x = -*x;
  386.     }
  387.     if (h->linbits)      
  388.         if ((h->ylen-1) == *y)
  389.         *y += hgetbits(h->linbits);
  390.     if (*y) {
  391.         if (hget1bit() == 1)
  392.         *y = -*y;
  393.     }
  394.     }
  395.     return error;  
  396. }
  397.